package com.github.hgkmail.hello.leetcode101.pointer.tree.trie;

public class LC208ImplementTriePrefixTree {
    //word 和 prefix 仅由小写英文字母组成
    public static class Trie {
        //节点，多叉树
        class TrieNode {
            boolean isWord; //是否单词
            TrieNode[] children; //索引
            TrieNode() {
                isWord = false;
                children=new TrieNode[26]; //26个字母，默认值null
            }
        }

        //伪节点
        TrieNode dummyHead;
        public Trie() {
            dummyHead = new TrieNode();
        }

        public void insert(String word) {
            if (word.length()<=0) {
                return;
            }
            char[] chars = word.toCharArray();
            TrieNode curr=dummyHead;
            for (int i = 0; i < chars.length; i++) {
                int index=chars[i]-'a';
                if (curr.children[index]==null) {
                    curr.children[index]=new TrieNode();
                }
                curr=curr.children[index];
            }
            curr.isWord=true;
        }

        public boolean search(String word) {
            if (word.length()<=0) {
                return true;
            }
            char[] chars = word.toCharArray();
            TrieNode curr=dummyHead;
            for (int i = 0; i < chars.length; i++) {
                int index=chars[i]-'a';
                if (curr.children[index]==null) {
                    return false;
                }
                curr=curr.children[index];
            }
            return curr != null && curr.isWord;
        }

        public boolean startsWith(String prefix) {
            if (prefix.length()<=0) {
                return true;
            }
            char[] chars = prefix.toCharArray();
            TrieNode curr=dummyHead;
            for (int i = 0; i < chars.length; i++) {
                int index=chars[i]-'a';
                if (curr.children[index]==null) {
                    return false;
                }
                curr=curr.children[index];
            }
            return curr!=null;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 True
        System.out.println(trie.search("app"));     // 返回 False
        System.out.println(trie.startsWith("app")); // 返回 True
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 True
    }
}
